package leetcode.array;

/**
 * @author Cheng Jun
 * Description: 给你一个 严格升序排列 的正整数数组 arr 和一个整数 k 。
 * <p>
 * 请你找到这个数组里第 k 个缺失的正整数。
 * https://leetcode.cn/problems/kth-missing-positive-number/
 * @version 1.0
 * @date 2022/8/8 13:40
 */
public class findKthPositive {


    int findKthPositive0(int[] arr, int k) {
        // [1] 1
        // 2
        // [2] 1
        // 1
        int k1 = 0;
        int num = 1;
        int index = 0;
        while (k1 < k) {
            // index 有效
            // num 等于 arr[index]; index++, num++
            // num 不等于 arr[index]; k1++ if(k == k1) return num, num++
            // index 无效; k1++ if(k == k1) return num, num++
            if (index < arr.length) {
                if (num == arr[index]) {
                    index++;
                    num++;
                } else {
                    if (++k1 == k) return num;
                    num++;
                }
            } else {
                if (++k1 == k) return num;
                num++;
            }
        }
        return -1;
    }

    // 假设这个数组是空的, 那么给的k就是所缺的数, 如果数组不空, 但是所有的数都大于k,
    // 那么这个数组缺失了1~k, k还是所缺的数. 数组中所有的数都小于k ,则判断有n个数,
    // k+n是所缺数 数组中有小于k的有大于k的, 比如{1,2,6,7}, 取k=4, 则在该判断中,
    // 经过1和2的后, k=6, 此时6和7也满足了条件, 于是k = 8居然也行了... k在每一个小于它的数那里获得+1,
    // 这个解法，我也不知道是怎么想出来的，技巧，只能是技巧
    public int findKthPositive1(int[] arr, int k) {
        int len = arr.length;
        for (int i = 0; i < len; i++) {
            if (arr[i] <= k) k++;
        }
        return k;
    }
}
